#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
template <typename T>
struct Node
{
    T data;
    int flag;
    Node<T> *next;
};

template <typename T>
class LinkedList
{
public:
    Node<T> *head;
    Node<T> *tail;
    int size;

    LinkedList()
    {
        head = NULL;
        tail = NULL;
        size = 0;
    }

    void push(T data)
    {
        Node<T> *temp = new Node<T>;
        temp->data = data;
        temp->flag = -1;
        temp->next = NULL;
        if (head == NULL)
        {
            head = temp;
            tail = temp;
            size++;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
    }

    void push(T data, int flag)
    {
        Node<T> *temp = new Node<T>;
        temp->data = data;
        temp->flag = flag;
        temp->next = NULL;
        if (head == NULL)
        {
            head = temp;
            tail = temp;
            size++;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
    }

    void pop()
    {
        if (head == NULL)
        {
            return;
        }
        else
        {
            Node<T> *temp = head;
            head = head->next;
            delete temp;
        }
    }

    void print()
    {
        Node<T> *current = head;
        while (current != NULL)
        {
            std::cout << current->data << std::endl;
            current = current->next;
        }
    }

    void insert(T data)
    {
        Node<T> *to_insert = new Node<T>;
        to_insert->data = data;
        to_insert->next = NULL;

        // 如果链表为空，直接插入
        if (head == NULL)
        {
            head = to_insert;
            return;
        }

        Node<T> *current = head;
        // 处理需要在头部插入的情况
        if (data < head->data)
        {
            to_insert->next = head;
            head = to_insert;
            return;
        }

        // 在链表中找到正确的插入位置
        while (current->next != NULL && current->next->data < data)
        {
            current = current->next;
        }

        to_insert->next = current->next;
        current->next = to_insert;
    }

    void delete_(T data)
    {
        // 处理空链表或需要删除头节点的情况
        if (head == NULL || head->data == data)
        {
            Node<T> *temp = head;
            head = head->next;
            delete temp;
            return;
        }

        Node<T> *current = head;
        while (current->next != NULL)
        {
            if (current->next->data == data)
            {
                Node<T> *temp = current->next;
                current->next = temp->next;
                delete temp; // 释放内存
                return;
            }
            current = current->next;
        }
    }
};

#endif // LINKEDLIST_H